// https://www.lintcode.com/problem/remove-nth-node-from-end-of-list/

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: The first node of linked list.
     * @param n: An integer
     * @return: The head of linked list.
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // write your code here
        ListNode h1 = head, h2 = head;
        ListNode prev = null;
        for (int i = 0; i < n; ++i) {
            h2 = h2.next;
        }
        while (h2 != null) {
            h2 = h2.next;
            prev = h1;
            h1 = h1.next;
        }
        if (null == prev) { // 删除的是head节点
            return head.next;
        }
        else {
            prev.next = h1.next;
            return head;
        }
        
    }
}